package leetcode.动态规划;

import org.junit.Test;

/**
 * @author :songyaozhang
 * @date :Created 2021/8/16 16:08
 * @description :https://leetcode-cn.com/problems/house-robber-ii/
 */
public class 打家劫舍II {
    @Test
    public void test() {
        Solution solution = new Solution();
        System.out.println(solution.rob(new int[]{1,2,3,1}));
    }

    class Solution {
        public int rob(int[] nums) {
            int n = nums.length;
            if (n == 0) return 0;
            if (n == 1) return nums[0];
            if (n == 2) return Math.max(nums[0], nums[1]);
            //从1到n
            //从0到n - 1
            return Math.max(rob0(0, nums, n - 1), rob0(1, nums, n));
        }

        private int rob0(int start, int[] nums, int n) {
            int[] dp = new int[n];
            dp[start] = nums[start];
            dp[start + 1] = Math.max(nums[start], nums[start + 1]);
            for (int i = start + 2; i < n; i++) {
                dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
            }
            return dp[n - 1];
        }
    }


}
